package shortest;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by zhonghongqiang on 2017-02-24.
 */
public class AllPath {

    public static void main(String[] args)
    {
        int MAX = 1001;
        int INF = Integer.MAX_VALUE;

        int[][] G = new int[MAX][MAX];
        int[] minD = new int[MAX];
        int minDist;
        Boolean[] finalSet = new Boolean[MAX];

        int N  = 9,M = 12;
        for(int i = 0; i < N; i++){
            finalSet[i] = false;
            minD[i] = INF;
            for(int j = 0; j < N; j++)
                G[i][j] = INF;
        }

        G[0][1] = G[1][0] = 1;
        G[0][3] = G[3][0] = 1;

        G[1][2] = G[2][1] = 1;
        G[1][4] = G[4][1] = 1;

        G[2][5] = G[5][2] = 1;

        G[3][4] = G[4][3] = 1;
        G[3][6] = G[6][3] = 1;

        G[4][7] = G[7][4] = 1;
        G[4][5] = G[5][4] = 1;

        G[5][8] = G[8][5] = 1;

        G[6][7] = G[7][6] = 1;

        G[7][8] = G[8][7] = 1;


        List<List<List<Integer>>> nodes = new ArrayList<>(N);


        // 设0为源点，计算从0到所有点的所有最短路径
        finalSet[0] = true;
        minD[0] = 0;
        // 首先把所有源点邻接点的最短距离初始化为源点到这些点的距离
        for(int i = 1; i < N; i++){
            if(G[0][i] != INF) {
                minD[i] = G[0][i];
                List<List<Integer>> minPaths = new ArrayList<>();
                minPaths.clear();
                List<Integer> pathList = new ArrayList<>();
                pathList.clear();
                pathList.add(0);
                pathList.add(i);
                minPaths.add(pathList);
                nodes.set(i, minPaths);
            }
        }

        // 从所有minD中找出最小的，并入集合S，重复N-1次（源点已经加入集合）
        for(int i = 1; i < N; i++){
            minDist = INF;
            int v = -1; // 记录到源点记录最小的结点
            for(int w = 1; w < N; w++){
                if(!finalSet[w] && minDist > minD[w]){
                    minDist = minD[w];
                    v = w;
                }
            }
            if(v == -1) break; // v = -1说明找不到点了，当图不连通时才会出现这种情况
            // 已经找到了到源点最近的点v，将其并入集合，并且考虑原来的最短距离0->...->W在加入了v之后有没有可能变短
            // 如果变短了，就更新为0->...>v->W
            finalSet[v] = true;
            for(int w = 1; w < N; w++){
                if(!finalSet[w]){
                    int newD = minDist + G[v][w];
                    if(newD < minD[w]){
                        minD[w] = newD;
                        List<List<Integer>> minPathsV = nodes.get(v);
                        List<Integer> pathList;
                        nodes.get(w).clear();
                        for(int index = 0; index < minPathsV.size(); index++){
                            pathList = minPathsV.get(index);
                            pathList.add(w);
                            nodes.get(w).add(pathList);
                        }

                    }else if(newD == minD[w]){
                        List<List<Integer>> minPathsV = nodes.get(v);
                        List<Integer> pathList;
                        for(int index = 0; index < minPathsV.size(); index++){
                            pathList = minPathsV.get(index);
                            pathList.add(w);
                            nodes.get(w).add(pathList);
                        }

                    }
                }
            }
        }
        for(int i = 1; i < N; i++){
            System.out.println("------------");
            System.out.println("0 to " + i + ":");
            System.out.println("The miniest distance:" + minD[i]);
            System.out.println("The possible paths:");
            List<List<Integer>> minPaths = nodes.get(i);
            int size = minPaths.size();
            List<Integer> pathList;
            for(int j = 0; j < size; j++){
                pathList = minPaths.get(j);
                int pathSize = pathList.size();
                for(int k = 0; k < pathSize - 1; k++){
                    System.out.println(pathList.get(k) + "->");
                }
                System.out.println(pathList.get(pathSize - 1));
            }

        }

    }
}
